//给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。 
//
// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 
//
// 
// 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 
// 
//
// 示例: 
//
// 输入: [1,2,3,0,2]
//输出: 3 
//解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 
// Related Topics 数组 动态规划 
// 👍 981 👎 0

package com.cute.leetcode.editor.cn;
public class BestTimeToBuyAndSellStockWithCooldown {
    public static void main(String[] args) {
        Solution solution = new BestTimeToBuyAndSellStockWithCooldown().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 天杀的动态规划
         * dp数组是一个[2][len]的数组
         * 这三个状态定义的是真的妙啊
         *
         * 需要用到三个状态：
         * 0：不持股且可以买入（可以是昨天不买的状态，也可以是昨天卖出的状态），可以由昨天的0和2得到
         * 1：持股（可以是今天买，可以是昨天买的），可以由昨天的1和0得到
         * 2：不持股且无法买入（只能是昨天持股今天卖出），只能由昨天的1得到
         *
         * 可以使用滚动变量模拟变化过程
         */
        public int maxProfit(int[] prices) {
            int len = prices.length;
            if (len<2) return 0;
            int[][] dp = new int[len][3];
            dp[0][0] = 0;
            dp[0][1] = -prices[0];
            dp[0][2] = 0;
            // dp[i][0]: 手上不持有股票，并且今天不是由于卖出股票而不持股，我们拥有的现金数
            // dp[i][1]: 手上持有股票时，我们拥有的现金数
            // dp[i][2]: 手上不持有股票，并且今天是由于卖出股票而不持股，我们拥有的现金数
            for (int i = 1; i < len ; i++) {
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);//可以转换到0的状态包括0和2
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);//状态1可以由昨天的0和1得到
                dp[i][2] = dp[i-1][1] + prices[i];//状态2只能由昨天的状态1得到
            }
            return Math.max(dp[len-1][0],dp[len-1][2]);
        }
        /**
         * 二刷，对状态定义没有整特别清楚
         */
        public int maxProfit2(int[] prices) {
            //一天之内定义三个状态
            //0：不持股且不是今天卖出（可由前一天的0，2推过来）
            //1：持股（可由前一天的0，1推过来）
            //2：不持股且今天卖出（可由前一天的1推过来）
            int[] pre = new int[3];
            int[] cur = new int[3];
            pre[1] = -prices[0];
            for (int i = 1; i<prices.length; i++){
                cur[0] = Math.max(pre[0], pre[2]);
                cur[1] = Math.max(pre[0] - prices[i], pre[1]);
                cur[2] = pre[1] + prices[i];//今天卖完明天冷冻期，所以不能推到1状态去
                pre = cur.clone();//克隆数组
            }
            return Math.max(cur[0], cur[2]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}